\documentclass[12pt]{article}

\usepackage[top=3cm, bottom=3cm, left=3cm, right=3cm]{geometry}      % [top=2cm, bottom=2cm, left=2cm, right=2cm]
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
\usepackage[parfill]{parskip}    
\usepackage{graphicx}
\usepackage{amssymb, amsmath, amsthm, amsfonts}
\usepackage{enumerate}
\usepackage{hyperref}

\newcommand{\adv}{\mathcal{A}}
\newcommand{\pr}{Prob}
\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\gen}{\class{Gen}}
\newcommand{\enc}{\class{Enc}}
\newcommand{\dec}{\class{Dec}}
\newcommand{\np}{\class{NP}}
\newcommand{\ip}{\class{IP}}
\newcommand{\zk}{\class{ZK}}
\newcommand{\pzk}{\class{PZK}}
\newcommand{\negl}{\class{negl}}
\newcommand{\poly}{\class{poly}}
\newcommand{\gni}{\class{GNI}}
\newcommand{\zo}{\{0, 1\}}
\newcommand{\vect}[1]{\textbf{#1}}
\newcommand{\zq}{\mathbb{Z}_q}
\newcommand{\cvect}[1]{(\vect{#1}_1, ... , \vect{#1}_k)}
\newcommand{\bL}{\bar{L}}
\newcommand{\Label}{\class{label}}
\newcommand{\ham}{\class{Ham}}


\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}

\begin{document}
\section{Collision Resistant Functions (CRF)}
Intuitively, a collision resistant function (CRF) $f$ is a function for which it is hard
to find two inputs s.t. their images collide: If $x_0 \neq x_1$, then with high probability $f(x_0) \neq f(x_1)$. Let us try to formalize the above:\\\\
\textbf{Attempt}  A function $f$ is $\epsilon(t)$-collision resistant if for any adversary $\adv$
running in time $t$:
\[ \pr[ (x,x') \leftarrow \adv(): x \neq x' \wedge f(x) = f(x')] < \epsilon(t) \]
The problem with the above definition is obvious. Assuming there exist $(x,x')$ that form a collision for $f$, an adversary $\adv$ that has $(x,x')$ hard-coded has a fast way to produce this collision. Therefore we give the following (asymptotic) definition:\\
\begin{definition}[(Asymptotic CRF] An ensemble $\mathbb{F} = \{F_n\}_{n \in \mathbb{N}}, F_n = \{f^n_i : D^n_i \rightarrow R^n_i\}_{i \in I_n}$ is collision resistant if there exist algorithms $G,E$ such that $G(1^n) \rightarrow i \in I$ is an index generation algorithm and $E(1^n, i, x \in D^n_i ) \rightarrow f_i(x)$, and for every non-uniform polynomial adversary $\adv$:

\[\pr[i \leftarrow G(1^n); (x,x') \leftarrow \adv(1^n,i): x \neq x' \wedge f(x) = f(x')] < \nu(n)\]
where $\nu(n)$ is a negligible function of $n$
\end{definition}
\textbf{Notes:}
\begin{itemize}
\item It is easy to see that any one-to-one function satisfies this requirement. However, we are interested in functions that are many-to-one, specifically, functions that map long inputs to short inputs, i.e., $|f(x)| < |x|$.
\item Unlike pseudorandom functions, we allow $\adv$ to receive $i$ as input, and still we require the hardness of finding collisions.
\item If $\mathbb{F}$ is CRF and at least two-to-one then $\mathbb{F}$ is one-way when viewed as a function from $I \times D$. Intuitively, if we can invert $\mathbb{F}$, then for any $(x,i)$ we can compute $f_i(x)$, find $y= f^{-1}_i(x)$, and with probability $\geq \frac{1}{2}$ we have $y \neq x$ and $f_i(y) = f_i(x)$ is a collision.
\item There exists two-to-one OWF which is not CR: For example, a OWF that ignores the last bit of its input.
\item There is no known construction of a CRF from OWF. Further, we have evidence that this is a hard task. It was proven that no such construction can use the OWF as a black-box. In fact, it is not even known that existence of TDPs implies existence of CRF.
\end{itemize}
We can construct CRF's from assumed hard problems such as discrete log or finding a "claw" in claw-free permutations as well as more direct constructions known as cryptographic hash functions using block ciphers or dedicated compression functions (MD5, SHA-1, RIPEMD ets.). 

\section{Message Authentication Codes}
Consider two parties \textit{A} and \textit{B} that wish to communicate over an open communication channel. This channel is untrusted: An adversary can inject, delete and modify messages at wish. The parties wish to be able to recognize when a received message is authentic, i.e., it was generated by the second party and not modified en route. A message authentication scheme consists of two interactive algorithms (ITM): \textit{auth} in the sender side and \textit{ver} in the receiver side, both initialized with the same shared (secret) key. Given a message $m$, $auth(k,m)$ generates an encoded version $e$. Since \textbf{no secrecy} is required, we can assume w.l.o.g. $e = (m, t)$ where $t$ is called a "tag". Given an encoded message $e = (m, t)$, $ver(k, m, t)$ outputs accept/reject.

We require consistency: \textit{ver} must accept any message encoded by \textit{auth}. Further, we require security: Any message not encoded by \textit{auth} should be rejected by \textit{ver}. This requirement, however, is not well defined since any encoded message can be potentially generated by an adversary. What we want is a definition that captures the notion of a ``session'' in the presence of an adversary that can interact with both parties, but still cannot produce valid tags for messages. To this end, we define the following game for an adversary $\adv$:

\begin{definition}[\textbf{MAC-GAME}(\textit{auth},\textit{ver},$\adv$,\textit{n})]
\begin{itemize}
\item Initialize shared random key $k \in \{0, 1\}^n$.
\item $\adv(1^n)$ interacts with \textit{auth} and \textit{ver} multiple (polynomial in $n$) times by querying $auth_k(m) \rightarrow (m, t)$ for any message $m$ he chooses, and queries $ver_k(m', t')$ for the validity of any pair $m',t'$ he also chooses.
\item $\adv$ wins if he produces a pair $(m^*,t^*)$ such that $auth_k$ was never queried on $m^*$ and $ver_k(m^*,t^*) =$ accept.
\end{itemize}
\end{definition}
We use the above defined MAC-GAME to define a MAC scheme as follows:

\begin{definition}[\textbf{MAC scheme}]
A MAC scheme is a pair of algorithms \textit{auth}, \textit{ver}, such that $auth_k(m) \rightarrow (m, t)$ is a tagging algorithm and $ver_k(m, t) = \{accept/reject\}$ is a verification algorithm. The algorithms must satisfy:
\begin{description}
\item[Consistency] $\forall k,m$: $ver_k(auth_k(m))=$ accept
\item[Security] $\forall$ PPT adversary $\adv$
\[ \pr[k \leftarrow \{0,1\}^n; \adv \text{ wins MAC-GAME}(auth,ver,\adv,n)] < \nu(n)\]
where $\nu(n)$ is a negligible function of $n$.
\end{description}
\end{definition}

\subsection*{Single-message MAC scheme}
We introduce a scheme that is secure for a single message against computation-
ally unbounded adversaries. First, we need the following definitions:
\begin{definition}
A family of functions $H = \{h_k : \{0, 1\}^m\}_{k \in \{0,1\}^a}$ is called \textit{pairwise independent} (or, \textit{2-universal}) if for any $ \alpha \neq \beta \in\{0,1\}^n, \gamma, \delta \in \{0, 1\}^m$:
\[ \pr[ k \leftarrow \{0,1\}^a; h_k(\alpha) = \gamma \wedge h_k(\beta) = \delta] = { 1 \over 2^{2m}}\]
\end{definition}

\begin{definition}
An ensemble of functions $\mathbb{H} = \{H_n\}_{n\in \mathbb{N}}$ of families of functions is \textit{pairwise independent} with any range $m(n)$ and key range $a(n)$ if $\forall n \in \mathbb{N}$ the family $H_n = \{h_k : \{0,1\}^n \rightarrow \{0,1\}^{m(n)}\}_{k \in \{0,1\}^{a(n)}}$ is pairwise independent.
\end{definition}

Let $\mathbb{H}$ be an ensemble of pairwise independent families. Consider the following scheme for $n$-bit messages:\\
Initialize random key $k \in \{0, 1\}^{a(n)}$. Define $auth(k,m) = m, h_k(m), ver(k, m, t) = I[t=h_k(m)]$, where $h_k \in H_n$.

\textbf{Claim:} The above scheme is secure for a single message.\\
\textbf{Proof:} Consistency is trivial. Security follows directly from the definition of \textit{pairwise independence}:\\ An adversary $\adv$ can query \textit{auth} once for some $\alpha: (\alpha,\gamma) \leftarrow auth(k,\alpha)$. To win $\adv$ needs to find a pair $\beta, \delta$ s.t. $ver(k,\beta,\delta) =$ accept. By the definition of \textit{auth}, \textit{ver} this implies: $h_k(\alpha) = \gamma \wedge h_k(\beta) = \delta$. Since $k$ is chosen at random, the probability of this event is:
\begin{align*}
  & \; \pr_k[h_k(\beta) = \delta | h_k(\alpha) = \gamma]\\
=&\; \pr_k[h_k(\beta) = \delta \wedge h_k(\alpha) = \gamma]/ \pr_k[h_k(\alpha) = \gamma]\\
=&\; 2^{-2m} \cdot 2^m = 2^{-m}
\end{align*}

\section{Symmetric Encryption}
Encryption, or guaranteeing secrecy of information, is perhaps the most basic task in cryptography. Yet, it is the hardest to capture mathematically. A pair of polynomial time algorithms $(ENC,DEC)$ is a symmetric encryption scheme if the following two conditions hold:
\begin{description}
\item[Correctness] Assuming a message domain $M$, for any $m \in M$, $DEC(k,ENC(k,m))= m$
\item[Secrecy] This proves to be a hard task. How do we define secrecy? Let us try to enumerate the things that we want to avoid the adversary doing:
\begin{itemize}
\item Adversary should not learn the secret key.
\item Adversary should not learn the message.
\item Adversary should not learn parts of the message (e.g. the first bit of the message).
\item Adversary should not learn any predicate of the message.
\item Adversary should not be able to recognize any relations between encrypted messages (e.g. he should not know if a message was sent twice).
\item Adversary should not be able to do the above even if she has some prior knowledge on the message (e.g. she knows that the message is written in English or that it is either "buy" or "sell").
\end{itemize} 
\end{description}
Since the list is too long and we never know when we "get it all" we try a different approach: describe an ideal scheme, where security will be obviously guaranteed. We say that an encryption scheme is secure if it "behaves like the ideal scheme" in the eyes of any feasible observer. Let us formalize this definitional approach.
\subsection{Semantic Security}
We formalize the definition in three steps:
\begin{itemize}
\item Formalize the real-life setting we are addressing
\item Formalize the ideal scheme
\item Formalize the notion of "behaves like the ideal scheme"
\end{itemize}
\textbf{Real-life scheme}\\
In a real-life scheme we have the following, assuming an external observer $E$:
\begin{enumerate}
\item \textit{E} draws $m$ from distribution $D$ and sends it to \textit{ENC}
\item Some information $Z(m)$ leaks to an adversary $A$
\item $A$ receives $c$ = $ENC(k,m)$
\item $A$ computes $v$ from $c,Z(m)$. (Intuitively, $v$ represents some value that $A$ learned on $m$.)
\item $E$ computes $P(m, v)$, where $P$ is a predicate. Intuitively, $P(m, v) = 1$ represents that the adversary $A$ indeed learned something about $m$.
\end{enumerate}
\textbf{Ideal scheme}\\
The ideal encryption process is the same as the real life process, except that the adversary, now called $S$ (simulator), does not receive the cipher $c$. Instead, it sees some leakage function $l$. This function represents the information that the scheme is allowed to leak on plaintext (a common example is $l(m)$ = $|m|$). More precisely:
\begin{enumerate}
\item $E$ sends $m \leftarrow D$ to $ENC$
\item Some information $Z(m),l(m)$ leaks to the adversary $S$
\item $S$ computes $v$ from $l(m),Z(m)$, and sends $v$ to $E$
\item $E$ computes $P(m, v)$, where $P$ is a predicate as above
\end{enumerate}
\textbf{``Behaves like the ideal scheme''}\\
Intuitively, when saying that a scheme "behaves like the ideal scheme", we want to say that from the point of view of any external observer the real scheme looks like the ideal scheme. Namely, for any adversary A that interacts with the real scheme there could be an adversary $S$ that interacts with the ideal scheme s.t no external process can tell the difference between the two cases. Formally:
\begin{definition} A symmetric encryption scheme (\textit{ENC,DEC)} is \textbf{semantically secure} with respect to message domain $M = \{M_n\}_{n\in \mathbb{N}}$ and leakage function $l$, if for any polytime adversary $\adv$ there exists a polytime simulator $S$ s.t for any sampling algorithm $D$ s.t support$(D(1^n)) \subset M_n$, any polytime auxiliary information function $Z$ and any polytime
predicate $P$:
\begin{align*} |\pr_{k \in \{0,1\}^n}[m \leftarrow D(1^n); c \leftarrow ENC(k,m); v \leftarrow \adv(c,Z(m)); P(m, v) = 1]\\ - \pr[m \leftarrow D(1^n); v \leftarrow S(l(m),Z(m)),P(m,v)=1]| < \nu(n)
\end{align*}
where $\nu(n)$ is some negligible function of $n$.
\end{definition}
The probability is taken also over the random coins of the relevant algorithms.\\
\textbf{Note:}  Since in this definition the scheme is secure for any auxiliary input functions $Z$, it does not matter if we model $\adv$ and $S$ as uniform or non-uniform poly-time adversaries (the advice can be included by $Z$).
\subsection{Security by Indistinguishability}
Even though semantic security seems like very intuitive notion, it is certainly cumbersome to work with. So instead we will see an alternative definition which is considerably simpler, and ends up being equivalent to semantic security. The definition involves a simple game where the adversary is tested for the ability to guess which message is encrypted in a given cipher-text. That is, given an encryption scheme $(ENC,DEC)$ for domain $M$, leakage function $l$ and an adversary $\adv$, define the following game:
\begin{itemize}
\item $\adv$ chooses two messages $m_0,m_1 \in M$ s.t $l(m_0) = l(m_1)$ 
\item A bit $b \leftarrow \{0, 1\}$ and a key $k \in \{0, 1\}^n$ are chosen at random and $c = ENC(k,m_b)$ is computed 
\item $\adv$ receives $c$
\item $\adv$ outputs a bit $b'$
\end{itemize}
We say that $\adv$ wins the game if $b = b'$.
\begin{definition}[\textbf{IND security}]
A symmetric encryption scheme $(ENC,DEC)$ is secure by indistinguishability with respect to message domain $M = \{M_n\}_{n\in\mathbb{N}}$ and leakage function $l$ if for any poly-time adversary $\adv$ we have:
\begin{align*} \pr_{k \in \{0,1\}^n}[b\leftarrow \{0,1\}; (m_0,m_1,s) \leftarrow \adv(1^n); b' \leftarrow \adv(1^n,ENC(k,m_b),s)\\ \text{s.t. } l(m_0) = l(m_1) \wedge b = b'] &< {1 \over 2} + \nu (n)
\end{align*}
where $\nu(n)$ is some negligible function of $n$.
\end{definition}
Surprisingly enough, these two notions of secrecy are equivalent. Formally we can state the following:
\begin{theorem}
A symmetric encryption scheme $\mathcal{E} = (ENC,DEC)$ is semantically secure with respect to domain $M$ and sampleable leakage function $l$ if and only if $\mathcal{E}$ is secure by indistinguishability for $M$ and $l$.
\end{theorem}
For proof see \url{http://www.cs.tau.ac.il/~canetti/f08-materials/scribe9.pdf}
\subsection{Security for Multiple Encryptions, CPA security}
The above definitions consider only the case where the adversary sees a single encryption of some message. When the adversary sees multiple messages it makes sense to ask how the messages to be encrypted are chosen. Two options are:
\begin{itemize}
\item Non-adaptively: all messages chosen in advance, before any cipher-text is known
\item Fully adaptively: each message is chosen after seeing the previous cipher-text
\end{itemize}
Given an encryption scheme for domain $M$ and leakage function $l$ and an adversary $\adv$, define the following IND-KPA game (indistinguishability under known plain-text attack):
\begin{itemize}
\item $\adv$ chooses $p$ pairs of messages $m_{1,0},m_{1,1},...,m_{p,0},m_{p,1} \in M$ s.t for all $i, l(m_{i,0}) = l(m_{i,1})$
\item $\adv$ receives $ENC(k,m_{1,b}),...,ENC(k,m_{p,b})$ for a random bit $b$
\item $\adv$ outputs a bit $b'$
\end{itemize}
We say that $\adv$ wins the game if $b' = b$

For the adaptive case, the IND-CPA game (for indistinguishability under chosen plain-text attack) is the same, except that $\adv$ generates the next pair of message only after seeing the previous ciphertext.

\begin{definition}
Let $\mathcal{E} = (ENC,DEC)$ be a symmetric encryption scheme. $\mathcal{E}$ is called IND-KPA secure (resp., IND-CPA secure) if any poly-time adversary wins the IND-KPA (resp., IND-CPA) game with probability at most $1/2+\nu(n)$ for some negligible function $\nu(n)$.
\end{definition}
\textbf{Notes:}\\
\begin{itemize}
\item If $\mathcal{E}$ is IND-secure and encryption is stateless, then it is IND-KPA secure.
\item IND-KPA security does not imply IND-CPA security (even for stateless schemes).
\end{itemize}
\end{document}












